"""
2320. 统计放置房子的方式数
已解答
中等
相关标签
相关企业
提示
一条街道上共有 n * 2 个 地块 ，街道的两侧各有 n 个地块。每一边的地块都按从 1 到 n 编号。每个地块上都可以放置一所房子。

现要求街道同一侧不能存在两所房子相邻的情况，请你计算并返回放置房屋的方式数目。由于答案可能很大，需要对 109 + 7 取余后再返回。

注意，如果一所房子放置在这条街某一侧上的第 i 个地块，不影响在另一侧的第 i 个地块放置房子。



示例 1：

输入：n = 1
输出：4
解释：
可能的放置方式：
1. 所有地块都不放置房子。
2. 一所房子放在街道的某一侧。
3. 一所房子放在街道的另一侧。
4. 放置两所房子，街道两侧各放置一所。
示例 2：


输入：n = 2
输出：9
解释：如上图所示，共有 9 种可能的放置方式。


提示：

1 <= n <= 104
"""
class P2320(object):
    def countHousePlacements(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [0]*(n+1)
        mod = 1000000007
        dp[0] = 1
        dp[1] = 2
        for i in range(2, n+1):
            dp[i] = (dp[i-1] + dp[i-2])%mod
        return int((dp[n] * dp[n])%mod)

print(P2320().countHousePlacements(2))
print(P2320().countHousePlacements(1000)) #500478595
print(1e9+7)
print(1000000007)

MOD = 10 ** 9 + 7
f = [1, 2]
for _ in range(10 ** 4 - 1):
    f.append((f[-1] + f[-2]) % MOD)

class Solution:
    def countHousePlacements(self, n: int) -> int:
        return f[n] ** 2 % MOD
